using namespace std;

#include <iostream>
#include <vector>
//#include <unordered_map>
namespace leetcode_136
{
    class Solution
    {
    public:
        int singleNumber(vector<int> &nums)
        {
            // 异或运算应用
            // 1. 一个整数跟自己异或，结果为0
            // 2. 任意一个整数跟0异或，结果为该整数本身
            // 3. 异或运算满足交换律，结合律
            // 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次
            // 空间复杂度：O(1)
            int res = 0;
            for (int num : nums)
                res ^= num;
            return res;
        }
    };

    void test_singleNumber()
    {
        Solution s;
        vector<int> nums{1, 2, 4, 1, 2}; // C++统一初始化
        //vector<int> nums { 2, 2, 3};
        int res = s.singleNumber(nums);
        cout << res << endl;
    }
} // namespace leetcode_136

namespace leetcode_25
{
    //25. K 个一组翻转链表
    /*
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

 

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

 

说明：

    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    class Solution
    {
    public:
        ListNode *reverseKGroup(ListNode *head, int k)
        {
            if (!head)
                return head;
            // 区间[a,b)包含k个待反转元素
            ListNode *a = head, *b = a;
            for (int i = 0; i < k; ++i)
            {
                // 不足k个元素，保持不变
                if (!b)
                    return head;
                b = b->next;
            }
            // 反转前k个元素
            ListNode *newHead = reverse(a, b);
            // 递归反转后续链表并连接起来
            a->next = reverseKGroup(b, k);
            return newHead;
        }

    private:
        // 区间[a,b)元素反转，注意是左闭右开
        ListNode *reverse(ListNode *a, ListNode *b)
        {
            ListNode *pre = NULL, *cur = a, *next = a;
            while (cur != b)
            {
                // 逐个反转
                next = cur->next;
                cur->next = pre;
                // 更新指针位置
                pre = cur;
                cur = next;
            }
            return pre;
        }
    };

    void printList(ListNode *head)
    {
        ListNode *cur = head;
        while (cur)
        {
            cout << cur->val;
            cur = cur->next;
            if (cur)
                cout << "-->";
        }
        cout << endl;
    }

    void releaseList(ListNode *head)
    {
        ListNode *cur = head;
        while (cur)
        {
            ListNode *tmp = cur;
            cur = cur->next;
            delete tmp;
        }
    }

    void test_reverseKGroup()
    {
        // [1,2,3,4,5]
        // 2
        // 初始化
        ListNode *head = new ListNode(1);
        ListNode *cur = head;
        for (int i = 2; i <= 5; i++)
        {
            ListNode *next = new ListNode(i);
            cur->next = next;
            cur = next;
        }
        cout << "init LinkList: ";
        printList(head);

        int k = 3;

        Solution s;
        ListNode *newHead = s.reverseKGroup(head, k);
        cout << "after reverseKGroup -- k=" << k << endl;
        cout << "LinkList: ";
        printList(newHead);

        releaseList(newHead);
    }
} // namespace leetcode_25

#include <algorithm>
#include <vector>
#include <iostream>
namespace leetcode_152
{
    // 152. 乘积最大子数组
    /*
* 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。


示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* 
* 
* 题解：动态规划思路
* 作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

    class Solution
    {
    public:
        int maxProduct_0(vector<int> &nums)
        {
            vector<int> maxF(nums), minF(nums);
            for (int i = 1; i < nums.size(); ++i)
            {
                maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
                minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
            }
            return *max_element(maxF.begin(), maxF.end());
        }

        int maxProduct(vector<int> &nums)
        {
            int maxF = nums[0], minF = nums[0], ans = nums[0];
            for (int i = 1; i < nums.size(); ++i)
            {
                int mx = maxF, mn = minF;
                maxF = max(mx * nums[i], max(nums[i], mn * nums[i]));
                minF = min(mn * nums[i], min(nums[i], mx * nums[i]));
                ans = max(maxF, ans);
            }
            return ans;
        }
    };

    void test_maxProduct()
    {
        vector<int> nums{2, 3, -2, 4};
        Solution s;
        int ret = s.maxProduct(nums);
        cout << ret << endl;

        vector<int> nums2{-2, 0, -1};
        ret = s.maxProduct(nums2);
        cout << ret << endl;

        vector<int> nums3{0, 2};
        ret = s.maxProduct(nums3);
        cout << ret << endl;

        vector<int> nums4{3, -1, 4};
        ret = s.maxProduct(nums4);
        cout << ret << endl;

        vector<int> nums5{-3, 2, -4};
        ret = s.maxProduct(nums5);
        cout << ret << endl;
    }
} // namespace leetcode_152

#include <unordered_map>
namespace leetcode_146
{
    /*
* 146. LRU缓存机制
* 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

    struct DLinkedNode
    {
        int key, value;
        DLinkedNode *prev;
        DLinkedNode *next;
        DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
        DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
    };

    class LRUCache
    {
    public:
        LRUCache(int capacity) : size(0), capacity(capacity)
        {
            // 使用伪头部尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head->next = tail;
            tail->prev = head;
        }

        int get(int key)
        {
            if (!cache.count(key))
                return -1;

            // 如果 key 存在，先通过哈希表定位，再移到头部
            DLinkedNode *node = cache[key];
            moveToHead(node);
            return node->value;
        }

        void put(int key, int value)
        {
            if (!cache.count(key))
            {
                // 如果 key 不存在，创建一个新的节点
                DLinkedNode *node = new DLinkedNode(key, value);
                // 添加进哈希表
                cache[key] = node;
                // 添加至双向链表的头部
                addToHead(node);
                ++size;
                if (size > capacity)
                {
                    // 如果超出容量，删除双向链表的尾部节点
                    DLinkedNode *removed = removeTail();
                    // 删除哈希表中对应的项
                    cache.erase(removed->key);
                    --size;
                }
            }
            else
            {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                DLinkedNode *node = cache[key];
                node->value = value;
                moveToHead(node);
            }
        }

    private:
        void moveToHead(DLinkedNode *node)
        {
            removeNode(node);
            addToHead(node);
        }

        void addToHead(DLinkedNode *node)
        {
            node->prev = head;
            node->next = head->next;
            head->next->prev = node;
            head->next = node;
        }

        DLinkedNode *removeTail()
        {
            DLinkedNode *node = tail->prev;
            removeNode(node);
            return node;
        }

        void removeNode(DLinkedNode *node)
        {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }

    private:
        unordered_map<int, DLinkedNode *> cache;
        DLinkedNode *head;
        DLinkedNode *tail;
        int size;
        int capacity;
    };

    void test_LRUCache()
    {
        LRUCache *cache = new LRUCache(2 /* 缓存容量 */);

        cache->put(1, 1);
        cache->put(2, 2);
        cout << cache->get(1) << endl; // 返回  1
        cache->put(3, 3);              // 该操作会使得密钥 2 作废
        cout << cache->get(2) << endl; // 返回 -1 (未找到)
        cache->put(4, 4);              // 该操作会使得密钥 1 作废
        cout << cache->get(1) << endl; // 返回 -1 (未找到)
        cout << cache->get(3) << endl; // 返回  3
        cout << cache->get(4) << endl; // 返回  4
    }
} // namespace leetcode_146

#include <string>
#include <assert.h>
#include <stack>
namespace leetcode_394
{
    // 394. 字符串解码
    /*
* 给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

    class Solution
    {
    public:
        // 左右括号匹配，堆栈
        string decodeString(string s)
        {
            stack<char> st;
            string res;
            for (char c : s)
            {
                if (c == ']')
                {
                    string s1;
                    // 如果是]，开始弹栈，直到[，得到字符串
                    while (st.top() != '[')
                    {
                        char c1 = st.top();
                        st.pop();
                        s1.insert(s1.begin(), c1);
                    }
                    st.pop(); // 弹出[
                    // 次数
                    int num = 0;
                    int deg = 1;
                    while (!st.empty() && isdigit(st.top()))
                    {
                        num += deg * (st.top() - '0');
                        st.pop();
                        deg *= 10;
                    }
                    // 如果是栈底，则构造解码字符串并添加到结果字符串，
                    // 否则，再次压栈
                    if (st.empty())
                    {
                        for (int i = 0; i < num; ++i)
                        {
                            res.append(s1);
                        }
                    }
                    else
                    {
                        for (int i = 0; i < num; ++i)
                        {
                            for (char c1 : s1)
                            {
                                st.push(c1);
                            }
                        }
                    }
                }
                else
                {
                    st.push(c);
                }
            }

            // 栈非空，直接弹栈，添加到结果字符串（注意顺序）
            if (!st.empty())
            {
                string s1;
                while (!st.empty())
                {
                    char c1 = st.top();
                    st.pop();
                    s1.insert(s1.begin(), c1);
                }
                res.append(s1);
            }

            return res;
        }
    };

    void test_decodeString()
    {
        Solution s;
        string str = s.decodeString("3[a]2[bc]");
        assert(str == "aaabcbc");

        str = s.decodeString("3[a2[c]]");
        assert(str == "accaccacc");

        str = s.decodeString("2[abc]3[cd]ef");
        assert(str == "abcabccdcdcdef");
    }
} // namespace leetcode_394

#include <assert.h>
#include <vector>
namespace leetcode_198
{
/*
* 198. 打家劫舍
* 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋
装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        // 动态规划思路求解：
        // dp[i]表示偷窃i号房屋时的最高金额
        // dp[0] = nums[0]
        // dp[1] = max(dp[-1] + nums[1], dp[0])
        // dp[2] = max(dp[0] + nums[2], dp[1])
        // dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        int dp_0 = 0;
        int dp_1 = nums[0];
        int dp_2;
        for(int i=1; i<nums.size(); ++i) {
            dp_2 = max(dp_0 + nums[i], dp_1);
            dp_0 = dp_1;
            dp_1 = dp_2;
        }
        return dp_2;
    }
};

void test_rob()
{
    Solution s;
    vector<int> nums1 {1,2,3,1};
    assert(4 == s.rob(nums1));

    vector<int> nums2 {2,7,9,3,1};
    assert(12 == s.rob(nums2));

    vector<int> nums3 {0};
    assert(0 == s.rob(nums3));
}
} // namespace leetcode_198


#include <assert.h>
#include <vector>
namespace leetcode_213
{
/*
* 213. 打家劫舍 II
* 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，
这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/ 

class Solution {
public:
    int rob(vector<int>& nums) {
        // 所有房屋围成圈，调整：
        // 将数组拆分成两个数组：一个从0到n-1，另一个从1到n，分别得到最大值后，再取最大。
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        vector<int> nums1(nums.begin(), nums.end()-1);
        vector<int> nums2(nums.begin()+1, nums.end());
        int ans1 = rob_1(nums1);
        int ans2 = rob_1(nums2);
        return max(ans1, ans2);
    }

private:
    int rob_1(vector<int>& nums) {
        // 动态规划思路求解：
        // dp[i]表示偷窃i号房屋时的最高金额
        // dp[0] = nums[0]
        // dp[1] = max(dp[-1] + nums[1], dp[0])
        // dp[2] = max(dp[0] + nums[2], dp[1])
        // dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        int dp_0 = 0;
        int dp_1 = nums[0];
        int dp_2;
        for(int i=1; i<nums.size(); ++i) {
            dp_2 = max(dp_0 + nums[i], dp_1);
            dp_0 = dp_1;
            dp_1 = dp_2;
        }
        return dp_2;
    }
};

void test_rob_ii()
{
    Solution s;
    vector<int> nums1 {2,3,2};
    assert(3 == s.rob(nums1));

    vector<int> nums2 {1,2,3,1};
    assert(4 == s.rob(nums2));

    vector<int> nums3 {3,1,7,8};
    assert(10 == s.rob(nums3));
}
} // namespace leetcode_213



namespace leetcode_337
{
/* 337. 打家劫舍 III
* 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 
除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */


// definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rob(TreeNode* root) {
        // 如果偷节点，就不能偷其左右子节点
        // 如果不偷该节点，则考虑偷其左右子节点
        // 比较两种方式的结果，谁大取谁
        return 0;
    }
};

void test_rob_iii()
{

}
} // namespace leetcode_337


#include <vector>
#include <assert.h>
#include <stack>
namespace leetcode_84
{
/*
* 84. 柱状图中最大的矩形
* 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

 

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* 
* 
*  三道单调栈练习题
    739. 每日温度
    496. 下一个更大元素 I
    42. 接雨水 这是三月份的一道打卡题，可以复习一波哈

*/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 单调栈：大于栈顶高度入栈，小于栈顶高度出栈，计算当前高度的面积
        // 面积的计算：当前高度所能覆盖的最大面积，当前高度*覆盖的宽度，覆盖的宽度=当前高度左右小于其高度的第一个柱子的下标之差
        heights.push_back(0); // 保证右边界为最后一个柱子，方便计算
        stack<int> s;
        int maxarea = 0;
        for(int i=0; i<heights.size(); ++i) {
            while(!s.empty() && heights[i] < heights[s.top()]) {
                int curheight = s.top();
                s.pop();
                int area = heights[curheight] * (!s.empty() ? (i-s.top()-1) : i);
                maxarea = max(maxarea, area);
            }
            s.push(i);
        }
        return maxarea;
    }
};


void test_largestRactangleArea()
{
    Solution s;
    vector<int> heights {2,1,5,6,2,3};
    assert(10 == s.largestRectangleArea(heights));
}


} // namespace leetcode_84





int main()
{
    // leetcode_136::test_singleNumber();
    // leetcode_25::test_reverseKGroup();
    // leetcode_152::test_maxProduct();
    // leetcode_146::test_LRUCache();
    //leetcode_394::test_decodeString();

    //leetcode_198::test_rob();
    //leetcode_213::test_rob_ii();

    leetcode_84::test_largestRactangleArea();

    return 0;
}